#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
	ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
	{
		ListNode* NewHead = new ListNode(-1);
		ListNode* cur = NewHead;
		while (pHead1 && pHead2)
		{
			if (pHead1->val < pHead2->val)
			{
				cur->next = pHead1;
				pHead1 = pHead1->next;
			}
			else
			{
				cur->next = pHead2;
				pHead2 = pHead2->next;
			}
			cur = cur->next;
		}
		if (pHead1)
			cur->next = pHead1;
		if (pHead2)
			cur->next = pHead2;
		ListNode* head = NewHead->next;
		delete NewHead;
		return head;
	}
};

